{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #寻找目标值 - 二维数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #divide-and-conquer #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #分治 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTargetIn2DPlants"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找目标值 - 二维数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>m</code>*<code>n</code> 的二维数组 <code>plants</code> 记录了园林景观的植物排布情况，具有以下特性：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每行中，每棵植物的右侧相邻植物不矮于该植物；</li>\n",
    "\t<li>每列中，每棵植物的下侧相邻植物不矮于该植物。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>请判断 <code>plants</code> 中是否存在目标高度值 <code>target</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>plants = [[2,3,6,8],[4,5,8,9],[5,9,10,12]], target = 8\n",
    "\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>plants = [[1,3,5],[2,5,7]], target = 4\n",
    "\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= m &lt;= 1000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>注意：本题与主站 240 题相同：<a href=\"https://leetcode-cn.com/problems/search-a-2d-matrix-ii/\" rel=\"noopener noreferrer\" target=\"_blank\">https://leetcode-cn.com/problems/search-a-2d-matrix-ii/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [er-wei-shu-zu-zhong-de-cha-zhao-lcof](https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [er-wei-shu-zu-zhong-de-cha-zhao-lcof](https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,3,6,8],[4,5,8,9],[5,9,10,12]]\\n8', '[[1,3,5],[2,5,7]]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        if not plants:\n",
    "           return False\n",
    "        i,j = len(plants[0])-1,0 # 左上角开始遍历\n",
    "        while i>=0 and j<len(plants):\n",
    "            if plants[j][i]==target:\n",
    "                return True\n",
    "            elif plants[j][i]<target:\n",
    "                j += 1\n",
    "            elif plants[j][i]>target:\n",
    "                i -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        m = len(plants)\n",
    "        if m == 0:\n",
    "            return False\n",
    "        n = len(plants[0])\n",
    "        if n == 0:\n",
    "            return False\n",
    "        x = 0\n",
    "        y = n - 1\n",
    "        while x<m and y >= 0:\n",
    "            if plants[x][y] == target:\n",
    "                return True\n",
    "            if plants[x][y] > target:\n",
    "                y -= 1\n",
    "            else:\n",
    "                x += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        # dp = []\n",
    "        # for plant in plants:\n",
    "        #     dp += plant\n",
    "        # return target in dp\n",
    "\n",
    "        # i, j = len(plants) - 1, 0\n",
    "        # while i >= 0 and j < len(plants[0]):\n",
    "        #     if plants[i][j] > target: i -= 1\n",
    "        #     elif plants[i][j] < target: j += 1\n",
    "        #     else: return True\n",
    "        # return False\n",
    "\n",
    "        if plants == []:\n",
    "            return False\n",
    "        elif not plants[0]:\n",
    "            return False\n",
    "        i,j = 0,len(plants[0])-1\n",
    "        while i < len(plants) and j >= 0:\n",
    "            if plants[i][j] < target: i += 1\n",
    "            elif plants[i][j] > target: j -=1\n",
    "            else: return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i = len(plants) -1 \n",
    "        j = 0\n",
    "        while i >= 0 and j <= len(plants[0])-1:\n",
    "            if plants[i][j] > target:\n",
    "                i -= 1\n",
    "            elif plants[i][j] < target:\n",
    "                j += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i,j=len(plants)-1,0\n",
    "        while i>=0 and j<len(plants[0]):\n",
    "            if plants[i][j]>target:\n",
    "                i=i-1\n",
    "            elif plants[i][j]<target:\n",
    "                j=j+1\n",
    "            else:return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        if plants == []:\n",
    "            return False\n",
    "        else:\n",
    "            h = 0\n",
    "            l = len(plants[0])-1\n",
    "            while l >= 0 and h < len(plants):\n",
    "                if plants[h][l] == target:\n",
    "                    return True\n",
    "                elif plants[h][l] < target:\n",
    "                    h += 1\n",
    "                else:\n",
    "                    l -= 1\n",
    "            return False\n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i, j = len(plants) - 1, 0\n",
    "        while i >= 0 and j < len(plants[0]):\n",
    "            if plants[i][j] > target: i -= 1\n",
    "            elif plants[i][j] < target: j += 1\n",
    "            else: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants, target):\n",
    "        if not plants or not plants[0]:\n",
    "            return False\n",
    "        \n",
    "        m, n = len(plants), len(plants[0])\n",
    "        \n",
    "        j, i = 0, n - 1\n",
    "        \n",
    "        while i >= 0 and j < m:\n",
    "            if plants[j][i] == target:\n",
    "                return True\n",
    "            elif plants[j][i] > target:\n",
    "                i = i - 1\n",
    "            else:\n",
    "                j = j + 1\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants, target: int) -> bool:\n",
    "        if not plants:return False\n",
    "        i,j=0,len(plants[0])-1\n",
    "        while i<len(plants) and j>=0:\n",
    "            if plants[i][j]>target:\n",
    "                j-=1\n",
    "            elif plants[i][j]<target:\n",
    "                i+=1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i, j = len(plants) - 1, 0\n",
    "        while i >= 0 and j < len(plants[0]):\n",
    "            if plants[i][j] > target: \n",
    "                i -= 1\n",
    "            elif plants[i][j] < target: \n",
    "                j += 1\n",
    "            else: \n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i,j=len(plants)-1,0\n",
    "        while i>=0 and j<len(plants[0]):\n",
    "            if plants[i][j]<target:\n",
    "                j+=1\n",
    "            elif plants[i][j]>target:\n",
    "                i-=1\n",
    "            else: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        if not plants:return False\n",
    "        m = len(plants)\n",
    "        n = len(plants[0])\n",
    "        res = False\n",
    "#        i,j = 0,n-1\n",
    "        for h in range(m):\n",
    "            if res == True:break\n",
    "            i,j = 0,n-1\n",
    "            while i <= j:\n",
    "                a = (i + j)//2\n",
    "                if plants[h][a] < target:i = a+1\n",
    "                elif plants[h][a] > target:j = a-1\n",
    "                else:\n",
    "                    res = True\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, matrix: List[List[int]], target: int) -> bool:\n",
    "        if not matrix:\n",
    "            return False\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        row, col = 0, n - 1\n",
    "        while row < m and col >= 0:\n",
    "            if matrix[row][col] == target:\n",
    "                return True\n",
    "            if matrix[row][col] < target:\n",
    "                row += 1\n",
    "            else:\n",
    "                col -= 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants, target):\n",
    "        i, j = len(plants) - 1, 0\n",
    "        while i >= 0 and j < len(plants[0]):\n",
    "            if plants[i][j] > target:\n",
    "                i -= 1\n",
    "            elif plants[i][j] < target:\n",
    "                j += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        for line in plants:\n",
    "            if target in line:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        if not plants: return False\n",
    "        line_num = len(plants)\n",
    "        col_num = len(plants[0])\n",
    "        i, j = 0, col_num - 1\n",
    "        while i < line_num and j >= 0:\n",
    "            if plants[i][j] < target: i += 1\n",
    "            elif plants[i][j] > target: j -= 1\n",
    "            else: return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        if not plants:\n",
    "            return False\n",
    "        i, j = 0, len(plants[0])-1\n",
    "        while i<=len(plants)-1 and j>=0:\n",
    "            if plants[i][j] == target:\n",
    "                return True\n",
    "            elif plants[i][j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        m=len(plants)\n",
    "        if m == 0:\n",
    "            return False\n",
    "        n = len(plants[0])\n",
    "        if n==0:\n",
    "            return False\n",
    "        \n",
    "        def erfen(listV, long, target):\n",
    "            l, r = 0, long-1\n",
    "            while l<=r:\n",
    "                mid = (r+l)//2\n",
    "                if listV[mid]<target:\n",
    "                    l = mid+1\n",
    "                elif listV[mid] == target:\n",
    "                    return True\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            return False\n",
    "        for i in range(m):\n",
    "            if erfen(plants[i], n, target):\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants, target):\n",
    "        for i in plants:\n",
    "            if target in i:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i, j = len(plants) - 1, 0\n",
    "        while i >= 0 and j < len(plants[0]):\n",
    "            if plants[i][j] == target:\n",
    "                return True\n",
    "            elif plants[i][j] > target:\n",
    "                i-=1\n",
    "            elif plants[i][j] < target:\n",
    "                j+=1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i,j=len(plants)-1,0\n",
    "        while True:\n",
    "            if i<0 or j>=len(plants[0]):\n",
    "                return False\n",
    "            elif plants[i][j]==target:\n",
    "                return True\n",
    "\n",
    "            if plants[i][j]<target:\n",
    "                j+=1\n",
    "            elif plants[i][j]>target:\n",
    "                i-=1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        m = len(plants)\n",
    "        if m == 0:\n",
    "            return False\n",
    "\n",
    "        n = len(plants[0])\n",
    "        if n == 0:\n",
    "            return False\n",
    "        i,j = 0,len(plants[0]) - 1\n",
    "        while i < m and j >= 0:\n",
    "            if plants[i][j] < target:\n",
    "                i += 1\n",
    "            elif plants[i][j] > target:\n",
    "                j -= 1\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i,j = len(plants)-1,0\n",
    "        while i >= 0 and j <= len(plants[0])-1:\n",
    "            if plants[i][j] > target:\n",
    "                i -= 1\n",
    "            elif plants[i][j] < target:\n",
    "                j += 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        i, j = len(plants) - 1, 0\n",
    "        while i >= 0 and j < len(plants[0]):\n",
    "            if target > plants[i][j]:\n",
    "                j += 1\n",
    "            elif target < plants[i][j]:\n",
    "                i -= 1\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTargetIn2DPlants(self, plants: List[List[int]], target: int) -> bool:\n",
    "        m=len(plants)\n",
    "        if m==0:\n",
    "            return False\n",
    "        n=len(plants[0])\n",
    "        if n==0:\n",
    "            return False\n",
    "        for i in range(m):\n",
    "            if target<plants[i][0]:\n",
    "                return False\n",
    "            if target>plants[i][-1]:\n",
    "                continue\n",
    "            l=0\n",
    "            r=n-1\n",
    "            while l<=r:\n",
    "                mid=(l+r)//2\n",
    "                if plants[i][mid]==target:\n",
    "                    return True\n",
    "                elif plants[i][mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid-1\n",
    "        return False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
